Problem statement: zenit11cki

i) (40 bodov)

V rámci boja proti intergalaktickému terorizmu sa budú v blízkej budúcnosti rušiť niektoré časopriestorové mosty. Je totiž potrebné zamedziť cestovanie a stretávanie sa nebezpečným živlom. Vstupom úlohy je intergalaktická mapa, kde sú zobrazené všetky galaxie s podozrením na výskyt rizikových obyvateľov. Medzi týmito galaxiami môžu existovať jednosmerné alebo dvojsmerné časopriestorové mosty, ktoré vytvárajú jediný spôsob prepravy. Cesta medzi dvoma galaxiami u a v existuje vtedy, ak existuje postupnosť mostov, ktoré nás z u prepraví do v. Cieľom vesmírnej bezpečnostnej organizácie je dosiahnuť, aby ak pre nejakú dvojicu galaxii u a v platilo, že existuje cesta z u do v, potom nesmie existovať cesta z v do u. Bezpečnostná organizácia chce zrušiť z každého dvojsmerného mostu práve jeden smer (uvedomte si, že dvojsmerný most nemôže ostať funkčný, lebo už sám o sebe je v konflikte so zámerom organizácie). Zistite, či je zámer organizácie pre danú intergalaktickú mapu uskutočniteľný.

Na prvom riadku vstupu je počet galaktických máp, ktoré nás zaujímajú (najviac 10, teroristických organizácii v rôznych častiach vesmíru je veľa). Popis každej mapy začína troma celými číslami: počet galaxii N (očíslovaných od 1 po N), počet jednosmerných mostov M a počet dvojsmerných mostov K. Platí, že N je medzi 1 a 50,000 vrátane a M+K je medzi 1 a 200,000 vrátane. Nasleduje M riadkov, na každom z nich dve rôzne čísla z rozsahu 1 a N, popisujúce číslo začiatočnej a koncovej galaxie daného jednosmerného mosta (v tomto poradí). Potom nasleduje K ďalších riadkov v rovnakom formáte, popisujúcich dvojsmerné mosty. Pre žiadnu dvojicu čísel neexistuje viac ako jeden transportný most (ak existuje jeden jednosmerný, potom určite neexistuje opačný jednosmerný a ani dvojsmerný a opačne). Pre každú mapu zistite, či je možné zrušiť práve jeden smer každého z dvojsmerných mostov tak, aby pre výslednú mapu platilo, že ak z nejakej galaxie u existuje cesta do nejakej galaxie v, potom neexistuje cesta z v do u. Na výstup vypíšte pre každú mapu do samostatného riadku existuje alebo neexistuje. Polovica vstupov bude mať M aj K nepresahujúce 10. V tejto úlohe je časový limit jedna sekunda. Za riešenie s časom exponenciálnym od parametrov N,M,K môžu byť tiež nejaké body.

Príklad:

Vstup:

4
3 3 0
1 2
2 3
3 1
3 2 0
1 2
2 3
3 0 3
1 2
2 3
3 1
3 1 2
1 2
2 3
1 3

Výstup:

neexistuje
existuje
existuje
existuje

V prvej mape nemáme žiadne dvojsmerné cesty, ale už samotné jednosmerné cesty, ktoré rušiť nemôžeme, znemožňujú dosiahnutie želaného stavu. V druhej mape opäť nemáme žiadne dvojsmerné mosty, ale jednosmerné nám v tomto prípade nevadia. V tretej mape musíme zjednosmerniť tri mosty. Jednou z možností je zrušiť smery 1->2, 2->3 a 1->3.